package com.gofaraway.service.左神算法课.tree;


/**
 * 二叉树的遍历
 * 前中后序
 * 递归序
 */
public class TraversalBinaryTree {

    static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }
    }


    /**
     * 前序遍历打印 二叉树
     * <p>
     * 如果一个节点在递归序中 第一次出现时打印出来 就是前序遍历
     *
     * @param node
     */
    public static void pre(Node node) {
        if (node == null) {
            return;
        }
        System.out.println(node.value);
        pre(node.left);
        pre(node.right);
    }


    /**
     * 中序遍历打印 二叉树
     * <p>
     * 如果一个节点在递归序中 第二次出现时打印出来 就是前序遍历
     *
     * @param node
     */
    public static void in(Node node) {
        if (node == null) {
            return;
        }
        pre(node.left);
        System.out.println(node.value);
        pre(node.right);
    }

    /**
     * 后遍历打印 二叉树
     * <p>
     * 如果一个节点在递归序中 第三次出现时打印出来 就是前序遍历
     *
     * @param node
     */
    public static void pos(Node node) {
        if (node == null) {
            return;
        }
        pos(node.left);
        pos(node.right);
        System.out.println(node.value);
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);

        pre(head);
        System.out.println("==========");
        in(head);
        System.out.println("==========");
        pos(head);

        //遍历结果
        /**
         * 前序
         * 1
         * 2
         * 4
         * 5
         * 3
         * 6
         * 7
         * ==========
         * 中序
         * 2
         * 4
         * 5
         * 1
         * 3
         * 6
         * 7
         * ==========
         * 后序
         * 4
         * 5
         * 2
         * 6
         * 7
         * 3
         * 1
         */
    }

}
